/**
 * 有若干价值为price，重量为weight的物品，以及一个总重量为all的背包，问最多能代走总价值为多少的物品。
 * weight 物品重量
 * price 物品价值
 * all 背包承重量
 * 动态规划和贪心算法类似，局部最优解推出最终最优解。
 */
public class DP_Test {
    public static void main(String[] args) {
        int[] weight = {2, 4, 1, 5, 2},price = {4, 5, 19, 3, 2}; //初始数据，其中weight[3]  price[3]共同代表了第三件物品的属性。
        int all = 6; //背包总容量
        System.out.println(dp(weight, price, all));
    }
    static int dp(int[] weight,int[] price,int all){
        int[][] dp = new int[price.length+1][all+1]; //由于dp的过程中会与上一项判断，所以我们将数组多定义一行和一列避免越界。
        /**
         * 此循环来用来遍历dp数组，dp数组的横轴代表着背包容量从1-6的过程，纵轴代表着不同的物品。
         * 我们一点一点的加背包容量，一点一点的加物品种类，
         * 最终用上了所有物品种类，背包容量为真实容量的dp[weight.length][all],就是最终解。
         */
        for (int i = 1; i <= weight.length; i++)    //加物品
            for (int j = 1; j <= all; j++)          //加背包容量
                /**
                 * j就是遍历到这里时候的背包容量，判断语句的前部分的意思是首先要保证这时候的背包容量能放得下这个物品。
                 * 后半部分是判断这个物品有没有必要放进去，dp[i-1][j-weight[i-1]]就是这个背包容量减去这个物品重量
                 * 时候的剩余重量，比如这时候背包容量为5，物品重量为3，就要去上一行没这个物品时候，背包容量为3的地方去找。
                 * 那个地方的价值就是那时候的最优解，再加上这个物品的价值，最后同相同背包容量没放上这个物品时候的价值相比较
                 * dp[i-1][j]就是指没放上这一行物品时候的价值。
                 * 如果价值更大则表示有必要放上这个物品，否则则放弃这个物品，用上一行相同容量时候的价值。
                 */
                if (j>=weight[i-1]&&dp[i-1][j-weight[i-1]]+price[i-1]>=dp[i-1][j])
                    dp[i][j] = dp[i-1][j-weight[i-1]]+price[i-1];
                else dp[i][j] = dp[i-1][j];
        return dp[weight.length][all]; //最后用上所有物品，用上所有背包的解就是最终解。
    }
}
